Search in Rotated Sorted Array
2020/4/19
問題概要
[0, 1, 2, 4, 5, 6, 7]みたいな配列があったとして、これが[4, 5, 6, 7, 0, 1, 2]のように、ある地点で分割されたあと入れ替わっている配列が渡される
これに対し、ある値がどのindexに存在するかを求めよ
制約
計算量はO(log N)以下に抑えなければならない
解法
計算量がO(N)で良いならもちろん全探索でok
ソート済み配列なら二分探索でO(log N)でok
ただ、今回はいずれの方法もとれないので工夫する必要がある、というのがこの問題の難しいところ。
ただ、nixii.iconが試したところ全探索でもTLE判定になるわけではなかった まずrotateして入れ替わってる配列のindexをpivot_index とする
これは二分探索で求める
次に、pivot_indexで配列をソート済み配列2つに切り分けられるので、pivot_indexが0のケースにも注意しつつ、こちらも二分探索
以上で計算量としてはO(log N)を満たせる
ただ、上記だと二分探索を2回行っている
解答を読むとこれを1回に減らす方法もある
こちらの方が簡単なコードだし理解しやすい気がする
(↓は冗長な印象)
code:solution.cpp
class Solution {
public:
int search(vector<int>& nums, int target) {
if (nums.size() < 1) return -1;
if (nums.size() == 1) {
return (nums0 == target) ? 0 : -1; }
// pivot's value should be minimum value in nums
int pivot = pivot_index(nums);
if (pivot == 0) return search(nums, 0, nums.size()-1, target);
if (nums0 <= target) return search(nums, 0, pivot-1, target); return search(nums, pivot, nums.size()-1, target);
}
int pivot_index(vector<int>& nums) {
int l = 0;
int r = nums.size() - 1;
if (numsl < numsr) return 0; while (l <= r) {
int pivot = (l + r) / 2;
if (numsl > numspivot) r = pivot - 1; else l = pivot + 1;
}
// if pivot_index exists, -1 will be never returned.
return -1;
}
int search(vector<int>& nums, int l, int r, int target) {
while (l <= r) {
int pivot = (l + r) / 2;
if (numspivot == target) return pivot; if (numspivot > target) r = pivot - 1; else l = pivot + 1;
}
return -1;
}
};